Efficient Seeds Computation Revisited
Identifieur interne : 006447 ( Main/Exploration ); précédent : 006446; suivant : 006448Efficient Seeds Computation Revisited
Auteurs : Michalis Christou [Royaume-Uni] ; Maxime Crochemore [Royaume-Uni, France] ; Costas S. Iliopoulos [Royaume-Uni, Australie] ; Marcin Kubica [Pologne] ; Solon P. Pissis [Royaume-Uni] ; Jakub Radoszewski [Pologne] ; Wojciech Rytter [Pologne] ; Bartosz Szreder [Pologne] ; Tomasz Wale [Pologne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 2011.
English descriptors
- KwdEn :
- Algorithm, Alternative algorithm, Array, Auxiliary array, Border array, Border seed, Cambridge university press, Canonical form, Chain maxgap problem, Chain maxgap problems, Computer science, Computeshortestseed algorithm, Corresponding seed, Data structure, Input string, Leaf list, Linear time, Linear time algorithm, Linear time algorithms, Longest array, Lseedm, Maxgap, Maxgap problem, Maxgaps, National science centre, Node, Period array, Pref, Right seed, Seed array, Seeds computation, Shortest, Shortest seed, Shortest seeds, Simple characterization, Stores elements, Time algorithm, Time complexity, Total size, Total time, Whole string.
- Teeft :
- Algorithm, Alternative algorithm, Array, Auxiliary array, Border array, Border seed, Cambridge university press, Canonical form, Chain maxgap problem, Chain maxgap problems, Computer science, Computeshortestseed algorithm, Corresponding seed, Data structure, Input string, Leaf list, Linear time, Linear time algorithm, Linear time algorithms, Longest array, Lseedm, Maxgap, Maxgap problem, Maxgaps, National science centre, Node, Period array, Pref, Right seed, Seed array, Seeds computation, Shortest, Shortest seed, Shortest seeds, Simple characterization, Stores elements, Time algorithm, Time complexity, Total size, Total time, Whole string.
Abstract
Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).
Url:
DOI: 10.1007/978-3-642-21458-5_30
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001422
- to stream Istex, to step Curation: 001422
- to stream Istex, to step Checkpoint: 000867
- to stream Main, to step Merge: 006824
- to stream Main, to step Curation: 006447
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient Seeds Computation Revisited</title><author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name></author><author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name></author><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></author><author><name sortKey="Kubica, Marcin" sort="Kubica, Marcin" uniqKey="Kubica M" first="Marcin" last="Kubica">Marcin Kubica</name></author><author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name></author><author><name sortKey="Radoszewski, Jakub" sort="Radoszewski, Jakub" uniqKey="Radoszewski J" first="Jakub" last="Radoszewski">Jakub Radoszewski</name></author><author><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name></author><author><name sortKey="Szreder, Bartosz" sort="Szreder, Bartosz" uniqKey="Szreder B" first="Bartosz" last="Szreder">Bartosz Szreder</name></author><author><name sortKey="Wale, Tomasz" sort="Wale, Tomasz" uniqKey="Wale T" first="Tomasz" last="Wale">Tomasz Wale</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:6C0A668C2EFEFF27F9DD326D65984E9A158771B3</idno><date when="2011" year="2011">2011</date><idno type="doi">10.1007/978-3-642-21458-5_30</idno><idno type="url">https://api.istex.fr/document/6C0A668C2EFEFF27F9DD326D65984E9A158771B3/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001422</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001422</idno><idno type="wicri:Area/Istex/Curation">001422</idno><idno type="wicri:Area/Istex/Checkpoint">000867</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">000867</idno><idno type="wicri:doubleKey">0302-9743:2011:Christou M:efficient:seeds:computation</idno><idno type="wicri:Area/Main/Merge">006824</idno><idno type="wicri:Area/Main/Curation">006447</idno><idno type="wicri:Area/Main/Exploration">006447</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Efficient Seeds Computation Revisited</title><author><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name><affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author><author><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name><affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation wicri:level="1"><country xml:lang="fr">France</country><wicri:regionArea>Université Paris-Est</wicri:regionArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author><author><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Australie</country><wicri:regionArea>Digital Ecosystems & Business Intelligence Institute, Curtin University of Technology, 6845, Perth, WA</wicri:regionArea><wicri:noRegion>WA</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author><author><name sortKey="Kubica, Marcin" sort="Kubica, Marcin" uniqKey="Kubica M" first="Marcin" last="Kubica">Marcin Kubica</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw</wicri:regionArea><wicri:noRegion>Warsaw</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation></author><author><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name><affiliation wicri:level="3"><country xml:lang="fr">Royaume-Uni</country><wicri:regionArea>Dept. of Informatics, King’s College London, WC2R 2LS, London</wicri:regionArea><placeName><settlement type="city">Londres</settlement><region type="country">Angleterre</region><region type="région" nuts="1">Grand Londres</region></placeName></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Royaume-Uni</country></affiliation></author><author><name sortKey="Radoszewski, Jakub" sort="Radoszewski, Jakub" uniqKey="Radoszewski J" first="Jakub" last="Radoszewski">Jakub Radoszewski</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw</wicri:regionArea><wicri:noRegion>Warsaw</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation></author><author><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw</wicri:regionArea><wicri:noRegion>Warsaw</wicri:noRegion></affiliation><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Dept. of Math. and Informatics, Copernicus University, Toruń</wicri:regionArea><wicri:noRegion>Toruń</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation></author><author><name sortKey="Szreder, Bartosz" sort="Szreder, Bartosz" uniqKey="Szreder B" first="Bartosz" last="Szreder">Bartosz Szreder</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw</wicri:regionArea><wicri:noRegion>Warsaw</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation></author><author><name sortKey="Wale, Tomasz" sort="Wale, Tomasz" uniqKey="Wale T" first="Tomasz" last="Wale">Tomasz Wale</name><affiliation wicri:level="1"><country xml:lang="fr">Pologne</country><wicri:regionArea>Dept. of Mathematics, Computer Science and Mechanics, University of Warsaw, Warsaw</wicri:regionArea><wicri:noRegion>Warsaw</wicri:noRegion></affiliation><affiliation wicri:level="1"><country wicri:rule="url">Pologne</country></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>2011</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term><term>Alternative algorithm</term><term>Array</term><term>Auxiliary array</term><term>Border array</term><term>Border seed</term><term>Cambridge university press</term><term>Canonical form</term><term>Chain maxgap problem</term><term>Chain maxgap problems</term><term>Computer science</term><term>Computeshortestseed algorithm</term><term>Corresponding seed</term><term>Data structure</term><term>Input string</term><term>Leaf list</term><term>Linear time</term><term>Linear time algorithm</term><term>Linear time algorithms</term><term>Longest array</term><term>Lseedm</term><term>Maxgap</term><term>Maxgap problem</term><term>Maxgaps</term><term>National science centre</term><term>Node</term><term>Period array</term><term>Pref</term><term>Right seed</term><term>Seed array</term><term>Seeds computation</term><term>Shortest</term><term>Shortest seed</term><term>Shortest seeds</term><term>Simple characterization</term><term>Stores elements</term><term>Time algorithm</term><term>Time complexity</term><term>Total size</term><term>Total time</term><term>Whole string</term></keywords><keywords scheme="Teeft" xml:lang="en"><term>Algorithm</term><term>Alternative algorithm</term><term>Array</term><term>Auxiliary array</term><term>Border array</term><term>Border seed</term><term>Cambridge university press</term><term>Canonical form</term><term>Chain maxgap problem</term><term>Chain maxgap problems</term><term>Computer science</term><term>Computeshortestseed algorithm</term><term>Corresponding seed</term><term>Data structure</term><term>Input string</term><term>Leaf list</term><term>Linear time</term><term>Linear time algorithm</term><term>Linear time algorithms</term><term>Longest array</term><term>Lseedm</term><term>Maxgap</term><term>Maxgap problem</term><term>Maxgaps</term><term>National science centre</term><term>Node</term><term>Period array</term><term>Pref</term><term>Right seed</term><term>Seed array</term><term>Seeds computation</term><term>Shortest</term><term>Shortest seed</term><term>Shortest seeds</term><term>Simple characterization</term><term>Stores elements</term><term>Time algorithm</term><term>Time complexity</term><term>Total size</term><term>Total time</term><term>Whole string</term></keywords></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: The notion of the cover is a generalization of a period of a string, and there are linear time algorithms for finding the shortest cover. The seed is a more complicated generalization of periodicity, it is a cover of a superstring of a given string, and the shortest seed problem is of much higher algorithmic difficulty. The problem is not well understood, no linear time algorithm is known. In the paper we give linear time algorithms for some of its versions — computing shortest left-seed array, longest left-seed array and checking for seeds of a given length. The algorithm for the last problem is used to compute the seed array of a string (i.e., the shortest seeds for all the prefixes of the string) in O(n 2) time. We describe also a simpler alternative algorithm computing efficiently the shortest seeds. As a by-product we obtain an O(nlog(n/m)) time algorithm checking if the shortest seed has length at least m and finding the corresponding seed. We also correct some important details missing in the previously known shortest-seed algorithm (Iliopoulos et al., 1996).</div></front></TEI><affiliations><list><country><li>Australie</li><li>France</li><li>Pologne</li><li>Royaume-Uni</li></country><region><li>Angleterre</li><li>Grand Londres</li></region><settlement><li>Londres</li></settlement></list><tree><country name="Royaume-Uni"><region name="Angleterre"><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name></region><name sortKey="Christou, Michalis" sort="Christou, Michalis" uniqKey="Christou M" first="Michalis" last="Christou">Michalis Christou</name><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name><name sortKey="Pissis, Solon P" sort="Pissis, Solon P" uniqKey="Pissis S" first="Solon P." last="Pissis">Solon P. Pissis</name></country><country name="France"><noRegion><name sortKey="Crochemore, Maxime" sort="Crochemore, Maxime" uniqKey="Crochemore M" first="Maxime" last="Crochemore">Maxime Crochemore</name></noRegion></country><country name="Australie"><noRegion><name sortKey="Iliopoulos, Costas S" sort="Iliopoulos, Costas S" uniqKey="Iliopoulos C" first="Costas S." last="Iliopoulos">Costas S. Iliopoulos</name></noRegion></country><country name="Pologne"><noRegion><name sortKey="Kubica, Marcin" sort="Kubica, Marcin" uniqKey="Kubica M" first="Marcin" last="Kubica">Marcin Kubica</name></noRegion><name sortKey="Kubica, Marcin" sort="Kubica, Marcin" uniqKey="Kubica M" first="Marcin" last="Kubica">Marcin Kubica</name><name sortKey="Radoszewski, Jakub" sort="Radoszewski, Jakub" uniqKey="Radoszewski J" first="Jakub" last="Radoszewski">Jakub Radoszewski</name><name sortKey="Radoszewski, Jakub" sort="Radoszewski, Jakub" uniqKey="Radoszewski J" first="Jakub" last="Radoszewski">Jakub Radoszewski</name><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><name sortKey="Rytter, Wojciech" sort="Rytter, Wojciech" uniqKey="Rytter W" first="Wojciech" last="Rytter">Wojciech Rytter</name><name sortKey="Szreder, Bartosz" sort="Szreder, Bartosz" uniqKey="Szreder B" first="Bartosz" last="Szreder">Bartosz Szreder</name><name sortKey="Szreder, Bartosz" sort="Szreder, Bartosz" uniqKey="Szreder B" first="Bartosz" last="Szreder">Bartosz Szreder</name><name sortKey="Wale, Tomasz" sort="Wale, Tomasz" uniqKey="Wale T" first="Tomasz" last="Wale">Tomasz Wale</name><name sortKey="Wale, Tomasz" sort="Wale, Tomasz" uniqKey="Wale T" first="Tomasz" last="Wale">Tomasz Wale</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006447 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006447 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:6C0A668C2EFEFF27F9DD326D65984E9A158771B3
|texte= Efficient Seeds Computation Revisited
}}
| This area was generated with Dilib version V0.6.33. |  |